|
A vantage-point tree, or VP tree is a BSP tree that segregates data in a metric space by choosing a position in the space (the "vantage point") and dividing the data points into two partitions: those that are nearer to the vantage point than a threshold, and those that are not. By repeatedly applying this procedure to partition the data into smaller and smaller sets, a tree data structure is created where neighbors in the tree are likely to be neighbors in the space. Peter Yianilos claimed that the VP-tree was discovered independently by him (Peter Yianilos) and by Jeffrey Uhlmann.〔 Yet, Uhlmann published this method before Yianilos in 1991. Uhlmann called the data structure a metric tree, the name VP-tree was proposed by Yianilos. Vantage point trees have been generalized to non-metric spaces using Bregman divergences by Nielsen et al. This iterative partitioning process is similar to that of a ''k''-d tree, but uses circular (or spherical, hyperspherical, etc.) rather than rectilinear partitions. In 2D Euclidean space, this can be visualized as a series of circles segregating the data. The VP tree is particularly useful in dividing data in a non-standard metric space into a BSP tree. ==Understanding a VP tree== The way a VP tree stores data can be represented by a circle.〔 First, understand that each node of this tree contains an input point and a radius. All the left children of a given node are the points inside the circle and all the right children of a given node are outside of the circle. The tree itself does not need to know any other information about what is being stored. All it needs is the distance function that satisfies the properties of the metric space. Just imagine a circle with a radius. The left children are all located inside the circle and the right children are located outside the circle. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Vantage-point tree」の詳細全文を読む スポンサード リンク
|